import java.util.HashMap;
import java.util.Map;

/**
 * 767.重构字符串
 */
public class Exerciser9 {
    public String reorganizeString(String s) {
        int n = s.length();
        Map<Character,Integer> hash = new HashMap<>();
        char maxValue = ' ';
        int maxCount = 0;
        for(int i = 0;i < n;i++) {
            char ch = s.charAt(i);
            hash.put(ch,hash.getOrDefault(ch,0) + 1);
            if(maxCount < hash.get(ch)) {
                maxCount = hash.get(ch);
                maxValue = ch;
            }
        }
        if(maxCount > (n + 1) / 2) {
            // 如果maxCount 次数大于整个s的长度一半还多，那么一定存在相邻的
            return "";
        }
        char[] ret = new char[n];
        int index = 0;
        for(int i = 0;i < maxCount;i++) {
            ret[index] = maxValue;
            index += 2;
        }
        hash.remove(maxValue);
        for(char ch : hash.keySet()) {
            for(int i = 0;i < hash.get(ch);i++) {
                if(index >= n) {
                    index = 1;
                }
                ret[index] = ch;
                index += 2;
            }
        }
        return new String(ret);
    }
}
